package Leetcode.链表;

import Leetcode.ListNode;

/**
 * 给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
 *
 * 示例 1:
 *
 * 输入: 1->2->3->4->5->NULL, k = 2
 * 输出: 4->5->1->2->3->NULL
 * 解释:
 * 向右旋转 1 步: 5->1->2->3->4->NULL
 * 向右旋转 2 步: 4->5->1->2->3->NULL
 */
public class L61_旋转链表或右移链表 {
    //先遍历求得链表总长度count，同时将链表首尾相连；
    //再找到原链表的倒数第k+1个节点，该节点的next就是新链表的头结点
    public ListNode rotateRight(ListNode head, int k) {
        if(k==0 || head==null || head.next==null) return head;

        int n;
        ListNode cur=head;
        //这里条件要注意是 cur.next !=null
        for(n=1; cur.next!=null; cur=cur.next)
            n++;
        cur.next = head;

        //loop = k%n 以上面例子，长度 5， k=2，那就是要在
        int move = n - k % n;
        for(int i=0; i<move; i++){
            cur = cur.next;
        }
        ListNode tmp = cur.next;
        cur.next = null;
        return tmp;
    }
}
